package daily.year2024.m10;

import java.util.List;

/**
 * 120.三角形最小路径和
 *
 * @author wjs 2024/10/22
 */
public class d22 {
    class Solution1 {
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.get(triangle.size()-1).size();
            int[] dp = new int[n];
            int[] tmp = new int[n];
            int res = 2147483647;
            for(List<Integer> list : triangle) {
                int m = list.size();
                for(int i=0;i < m;i++) {
                    if(i == 0) {
                        tmp[i] = dp[i] + list.get(i);
                    } else if(i == m-1) {
                        tmp[i] = dp[i-1] + list.get(i);
                    }else {
                        tmp[i] = Math.min(dp[i] + list.get(i),dp[i-1] + list.get(i));
                    }
                }
                int[] tmp2 = dp;
                dp = tmp;
                tmp = tmp2;
            }
            for(int t : dp) {
                res = Math.min(res,t);
            }
            return res;
        }
    }
}
